import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        TestSingleList testSingleList1 = new TestSingleList();
        testSingleList1.addLast(12);
        testSingleList1.addLast(23);
        testSingleList1.addLast(34);
        testSingleList1.addLast(45);
        testSingleList1.display();
        testSingleList1.printList();
        //testSingleList1.printList(testSingleList1.head);
    }
    public static void main3(String[] args) {
        //底层是一个双向链表  不是单链表
        LinkedList<Integer> list = new LinkedList<>();
    }
    //例4：将两个有序表合并成一个
    public static TestSingleList.ListNode mergeTwoLists(TestSingleList.ListNode head1, TestSingleList.ListNode head2){
        TestSingleList.ListNode newHead = new TestSingleList.ListNode(-1);//傀儡节点 虚拟节点
        TestSingleList.ListNode tmp = newHead;

        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }
        }
        //1.head1 = null     2.head2 = null
        if(head1 != null){
            tmp.next = head1;
        }
        if(head2 != null){
            tmp.next = head2;
        }
        return newHead.next;
    }

//例6：相交链表
    public static TestSingleList.ListNode getIntersectionNode(TestSingleList.ListNode headA, TestSingleList.ListNode headB) {
        //1.分别求两个链表长度
        int lenA = 0;
        int lenB = 0;
        TestSingleList.ListNode pl = headA;//pl 代表永远指向长的链表
        TestSingleList.ListNode ps = headB;//ps 代表永远指向短的链表
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //1.pl 代表永远指向长的链表  2.ps 代表永远指向短的链表  3.len 一定是一个正数
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //4.pl走了差值步
        while(pl != ps ){
            pl = pl.next;
            ps = ps.next;
        }
//        if(pl == null){
//            return null;
//        }
        return pl;
    }
    private static void createCut(TestSingleList.ListNode head1, TestSingleList.ListNode head2){
        head2.next = head1.next.next;
    }

    public static void main2(String[] args) {
        TestSingleList testSingleList1 = new TestSingleList();
        testSingleList1.addLast(12);
        testSingleList1.addLast(23);
        testSingleList1.addLast(34);
        testSingleList1.addLast(45);
        testSingleList1.display();

        TestSingleList testSingleList2 = new TestSingleList();
        testSingleList2.addLast(1);
        testSingleList2.addLast(3);
        testSingleList2.addLast(9);
        testSingleList2.addLast(100);
        testSingleList2.display();

        createCut(testSingleList1.head,testSingleList2.head);

        TestSingleList.ListNode ret = getIntersectionNode(testSingleList1.head,testSingleList2.head);
        System.out.println(ret.val);
//        TestSingleList.ListNode ret = mergeTwoLists(testSingleList1.head,testSingleList2.head);
//        testSingleList1.display(ret);
    }




    public static void main1(String[] args) {
        TestSingleList testSingleList = new TestSingleList();
        //testSingleList.createList();
        //为了打断点
        //System.out.println("sfasafa");
        //验证头插法
//        testSingleList.addFirst(12);
//        testSingleList.addFirst(23);
//        testSingleList.addFirst(34);
//        testSingleList.addFirst(45);
        //验证尾插法
        testSingleList.addLast(12);
        testSingleList.addLast(23);
        testSingleList.addLast(12);
        testSingleList.addLast(45);
        testSingleList.display();
        //验证根据index插入
        //testSingleList.addIndex(0,99);
        //testSingleList.display();
        //验证remove
//        testSingleList.remove(12);
//        testSingleList.display();
        //验证removeAllKey
//        testSingleList.removeAllKey(12);
//        testSingleList.display();
        //验证清空链表
//        testSingleList.clear();
//        testSingleList.display();
        //验证是否包含
        //System.out.println(testSingleList.contains(10));
        //验证长度
        //System.out.println(testSingleList.size());
        //翻转链表
//        TestSingleList.ListNode ret = testSingleList.reverseList();
//        testSingleList.display(ret);
        //找倒数第k个
//        TestSingleList.ListNode ret = testSingleList.findKthToTail(2);
//        System.out.println(ret.val);

    }
}
